Since network devices in a wireless network (WN) can be recognized by addresses uniquely assigned during network subscription process, it is desired to uniquely allocate addresses to the network devices with low message overhead and low power in order to build a large-scale WN comprising battery-powered network devices.
ZigBee, a representative WN device, provides a distributed address allocation mechanism (DAAM) for a cluster tree structure described below in order to reduce signaling overhead during a network subscription process [1]. All devices share a number of maximum child devices, Cm, a number of maximum child routers, Rm, and a maximum network depth Lm, which are pre-determined before the construction of a network. Each router has Cm independent addresses available for network subscription in a balanced tree structure, wherein Rm independent addresses may be available for allocation to child routers and the remaining, i.e., (Cm-Rm), independent addresses may be available for allocation to child end devices. Each device first selects a parent device among parent candidates (i.e., routers within a communication range) and requests the parent device for subscription as a child router. If subscription is denied by all parent candidates, each device then requests for subscription as a child end device. A router requested as a parent device can accept a device if it has an address available for allocation to a device (i.e., a router or an end device) requesting for subscription. Then the router allocates an address to the device, and establishes a parent-child relationship with the device.
Also, ZigBee provides a stochastic address allocation technique [1]. The stochastic address allocation technique does not provide each router independent addresses available for subscription, but it allows a router being requested as a parent device to arbitrarily select an address in entire address space and to allocate it to a device requesting for subscription. Then, the router broadcasts a message including information on the allocated address to all devices in a network to verify whether the allocated address is previously allocated to another device or not, and when it is determined that the allocated address is previously allocated to another device, the router repeats the address allocation process. 6LoWPAN, a new Internet-based WN system, suggests a technique for detecting validity of address allocation, wherein each device arbitrarily selects an address in entire address space by itself and then directly requests a coordinator, which has address information of all devices, for confirmation whether the selected address is previously used by another device [2]. This technique allocates an address to each device in a centralized manner.
Non-patent documents that are prior arts described above are as follows.    (Non-Patent Document 1)[1] ZigBee Alliance, “ZigBee specification,” www.zigbee.org, January 2008.    (Non-Patent Document 2)[2] Z. Shelby, et al, “Neighbor discovery optimization for low power and lossy networks (6LoWPAN), IETF Internet draft, May 2011.